package com.kuang.sort;


/*  堆排序 */

import java.util.concurrent.ThreadLocalRandom;

/**
 * @author kjx
 */
public class HeapSort {

    //全局变量数组长度
    private static int len;     //这个不用全局变量多加一个参数不断传递也可以

    public static int[] heapSort(int[] array) {
        len = array.length;
        /*  先建立最大堆  */
        buildMaxHeap(array);
        /*  随后不断将最大值丢到最后一位，并且将最后一位排除出去反复调整  */
        while (len > 0) {
            swap(array, 0, len - 1);
            len--;
            adjustHeap(array, 0);
        }
        return array;
    }


    /*  建立最大堆   */
    private static void buildMaxHeap(int[] array) {
        /*  从最后一个非叶节点向上不断调整 */
        for (int i = len / 2 - 1; i >= 0; i--) {
            adjustHeap(array, i);
        }
    }


    /*  调整堆 */
    private static void adjustHeap(int[] array, int i) {
        int maxIndex = i;
        int left = 2 * i + 1;
        int right = 2 * (i + 1);
        /*  如果有左子树，则进行比较    */
        if (left < len && array[left] > array[maxIndex]) {
            maxIndex = left;
        }
        /*  右子树同理   */
        if (right < len && array[right] > array[maxIndex] && array[right] > array[left]) {
            maxIndex = right;
        }
        /*  如果父节点不是最大值，则进行交换且递归调整下面的    */
        if (maxIndex != i) {
            swap(array, maxIndex, i);
            adjustHeap(array, maxIndex);
        }
    }


    //交换数组两个元素
    public static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }


    public static void main(String[] args) {
        int size = 20; // 数组大小
        int[] array = new int[size];

        for (int i = 0; i < size; i++) {
            array[i] = ThreadLocalRandom.current().nextInt(100); // 生成0到99的随机整数
        }

        /*  排序之前的数组 */
        for (int i : array) {
            System.out.print(i + " ");
        }

        System.out.println(" ");

        /*  堆排序   */
        heapSort(array);
        for (int i : array) {
            System.out.print(i + " ");
        }

    }
}
